//给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
//
// 正数的平方根有两个，只输出其中的正数平方根。
//
// 如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
//
//
//
// 示例 1:
//
//
//输入: x = 4
//输出: 2
//
//
// 示例 2:
//
//
//输入: x = 8
//输出: 2
//解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
//
//
//
//
// 提示:
//
//
//
// 0 <= x <= 2³¹ - 1
//
//
//
//
//
// 注意：本题与主站 69 题相同： https://leetcode-cn.com/problems/sqrtx/
//
// Related Topics 数学 二分查找 👍 51 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function mySqrt(x: number): number {

    //? 整数x的平方根一定是在1到x的范围内
    let left = 1,
        right = x;
    while (left <= right) {
        //? 中间值  下面这样写是防止溢出
        let mid = left + ((right - left) >> 1);
        //? 判断mid的平方是否小于或等于x，如果mid的平方小于x
        if (mid <= x / mid) {
            //? 判断(mid+1)的平方是否大于x，如果(mid+1)的平方大于x，那么mid就是x的平方根
            if (mid + 1 > x / (mid + 1)) {
                return mid;
            }
            //? 如果mid的平方小于x并且(mid+1)的平方小于x，那么x的平方根比mid大，接下来搜索从mid+1到x的范围
            left = mid + 1;
        } else {
            //? 如果mid的平方大于x，则x的平方根小于mid，接下来搜索1到mid-1的范围
            right = mid - 1;
        }
    }
    //? 如果输入参数是0，left等于1而right等于0，就直接返回0
    return 0;


};
//leetcode submit region end(Prohibit modification and deletion)
